package graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * @BelongsProject: leetcode
 * @BelongsPackage: graph
 * @author: 肖
 * @date: 2022/2/2 10:30
 * @Description: 迪杰斯特拉算法
 * @since JDK 11
 */

public class Dijkstra {
    public static HashMap<NodeG,Integer> dijkstra(NodeG from){
//      从head到其他节点的最短距离
        HashMap<NodeG,Integer> distinceMap = new HashMap<NodeG,Integer>();
        distinceMap.put(from,0);
//      已经求过最小的放在selectNodes里面
        HashSet<NodeG> selectNodes = new HashSet<>();
        NodeG minNode = getMinDistanceAndUnselectedNode(distinceMap,selectNodes);
        while(minNode != null){
            int distance = distinceMap.get(minNode);
            for (Edge edge :minNode.edges){
                NodeG toNode = edge.to;
                if(!distinceMap.containsKey(toNode)){
                    distinceMap.put(toNode,distance+ edge.weight);
                }else {
                    distinceMap.put(edge.to,Math.min(distinceMap.get(toNode),distance+edge.weight));
                }
            }
            selectNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distinceMap,selectNodes);
        }
        return distinceMap;
    }

    private static NodeG getMinDistanceAndUnselectedNode(HashMap<NodeG, Integer> distinceMap, HashSet<NodeG> selectNodes) {
        NodeG minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for(Map.Entry<NodeG, Integer> entry :distinceMap.entrySet()){
            NodeG node = entry.getKey();
            int distance = entry.getValue();
            if(!selectNodes.contains(node) && distance<minDistance){
                minNode = node;
                minDistance= distance;
            }
        }
        return minNode;
    }
}
